/*************************************************************************
	> File Name: black_red_tree.cpp
	> Author: 
	> Mail: 
	> Created Time: Thu 15 Aug 2024 06:41:25 PM CST
 ************************************************************************/

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define NIL (&__NIL)
#define RED 0
#define BLACK 1
#define DBLACK 2
#define HAS_RED has_red_node
#define L(n) (n->lchild)
#define R(n) (n->rchild)
#define C(n) (n->color)
#define K(n) (n->key)

typedef struct Node {
	int key, color;
	struct Node *lchild, *rchild;
} Node;

Node __NIL;
__attribute__((constructor))
void init_NIL() {
	NIL->key = -1;
	NIL->color = BLACK;
	NIL->lchild = NIL->rchild = NIL;
	return ;
}

Node *getNewNode(int key) {
	Node *p = (Node *)malloc(sizeof(Node));
	p->key = key;
	p->color = RED;
	p->lchild = p->rchild = NIL;
	return p;
}

bool HAS_RED(Node *root) {
	return C(L(root)) == RED || C(R(root)) == RED;
}
// 红色上浮
void redUp(Node *root) {
	C(root) = RED;
	C(L(root)) = C(R(root)) = BLACK;
	return ;
}

Node *leftRotate(Node *root) {
	Node *new_root = root->rchild;
	root->rchild = new_root->lchild;
	new_root->lchild = root;
	return new_root;
}

Node *rightRotate(Node *root) {
	Node *new_root = root->lchild;
	root->lchild = new_root->rchild;
	new_root->rchild = root;
	return new_root;
}

Node *insertMaintain(Node *root) {
	int flag = 0;
	if(C(L(root)) == RED && HAS_RED(L(root))) flag = 1;
	if(C(R(root)) == RED && HAS_RED(R(root))) flag = 2;
	if(flag == 0) return root;
	if(C(L(root)) == RED && C(R(root)) == RED) {
		redUp(root); 
		return root;
	}
	if(flag == 1) {
		if(C(R(L(root))) == RED) L(root) = leftRotate(L(root));
		root = rightRotate(root);
	} else {
		if(C(L(R(root))) == RED) R(root) = rightRotate(R(root));
		root = leftRotate(root);
	}
	redUp(root);
	return root;
}

Node *__insert(Node *root , int key) {
	if(root == NIL) return getNewNode(key);
	if(key == root->key) return root;
	if(key < root->key) root->lchild = __insert(root->lchild, key);
	else root->rchild = __insert(root->rchild, key);
	return insertMaintain(root);
}

Node *insert(Node *root, int key) {
	root = __insert(root, key);
	root->color = BLACK;
	return root;
}

Node *preDecessor(Node *root) {
	Node *temp = root->lchild;
	while(temp->rchild != NIL) temp = temp->rchild;
	return temp;
}

Node *eraseMaintain(Node *root) {
	if(C(L(root)) != DBLACK && C(R(root)) != DBLACK) return root;
	// brother is red
	if(HAS_RED(root)) {
		root->color = RED;
		if(C(L(root)) == RED) {
			root = rightRotate(root);
			root->rchild = eraseMaintain(root->rchild);
		} else {
			root = leftRotate(root);
			root->lchild = eraseMaintain(root->lchild);
		}
		root->color = BLACK;
		return root;
	}
	// brother is black
	if(C(L(root)) == DBLACK && !HAS_RED(R(root))
	|| C(R(root)) == DBLACK && !HAS_RED(L(root))) {
		root->color += 1;
		C(L(root)) -= 1;
		C(R(root)) -= 1;
		return root;
	}
	// LR / LL
	if(C(R(root)) == DBLACK) {
		C(R(root)) = BLACK;
		if(C(L(L(root))) != RED) {
			L(root) = leftRotate(L(root));
		}
		C(L(root)) = C(root);
		root = rightRotate(root);
		C(L(root)) = C(R(root)) = BLACK;
	} else { // RL / RR
		C(L(root)) = BLACK;
		if(C(R(R(root))) != RED) {
			R(root) = rightRotate(R(root));
		}
		C(R(root)) = C(root);
		root = leftRotate(root);
		C(L(root)) = C(R(root)) = BLACK;
	}
	return root;
}

Node *__erase(Node *root, int key) {
	if(root == NIL) return root;
	if(key < root->key) {
		root->lchild = __erase(root->lchild, key);
	}
	else if(key > root->key) {
		root->rchild = __erase(root->rchild, key);
	}
	else {
		if(root->lchild ==NIL || root->rchild == NIL) {
			Node *temp = (root->lchild == NIL) ? root->rchild : root->lchild;
			temp->color += root->color;
			free(root);
			return temp;
		}
		Node *temp = preDecessor(root);
		root->key = temp->key;
		root->lchild == __erase(root->lchild, temp->key);
	}
	return eraseMaintain(root);
}

Node *erase(Node *root, int key) {
	root = __erase(root, key);
	root->color = BLACK;
	return root;
}

void preOrder(Node *root) {
	if(root == NIL) return ;
	printf("(%d)->[ %d | %d , %d ]\n", 
		C(root), K(root), 
		K(L(root)), K(R(root))
	);
	preOrder(L(root));
	preOrder(R(root));
	return ;
}

void clearRoot(Node *root) {
	if(root == NIL) return ;
	clearRoot(root->lchild);
	clearRoot(root->rchild);
	free(root);
	return ;
}
int main() {
	srand(time(0));
	Node *root = NIL;
	#define MAX_N 10
	for(int i = 0; i < MAX_N; i++) {
		root = insert(root, rand() % 100);
	}
	preOrder(root);
	
	int x;
	while(~scanf("%d", &x)) {
		if(x == -1) break;
		root = erase(root, x);
		preOrder(root);
	}
	clearRoot(root);
	return 0;
}